Minimum insertion steps to make a string palindrome [Longest Common Subsequence]

Time: O(N^2); Space: O(N); hard

Given a string s. In one step you can insert any character at any index of the string.

Return the minimum number of steps to make s palindrome.

A Palindrome String is one that reads the same backward as well as forward.

Example 1:

Input: s = “zzazz”

Output: 0

Explanation:

The string “zzazz” is already palindrome we don’t need any insertions.

Example 2:

Input: s = “mbadm”

Output: 2

Explanation:

  • String can be “mbdadbm” or “mdbabdm”.

Example 3:

Input: s = “leetcode”

Output: 5

Explanation:

  • Inserting 5 characters the string becomes “leetcodocteel”.

Example 4:

Input: s = “g”

Output: 0

Example 5:

Input: s = “no”

Output: 1

Constraints:

  • 1 <= len(s) <= 500

  • All characters of s are lower case English letters.

Hints:

  1. Is dynamic programming suitable for this problem ?

  2. If we know the longest palindromic sub-sequence is x and the length of the string is n then, what is the answer to this problem? It is n - x as we need n - x insertions to make the remaining characters also palindrome.

[2]:

### 1. Dynamic programming [O(N^2), O(N)]

[3]:

class Solution1(object):
    """
    Time: O(N^2)
    Space: O(N)
    """
    def minInsertions(self, s):
        """
        :type s: str
        :rtype: int
        """
        def longestCommonSubsequence(text1, text2):

            if len(text1) < len(text2):
                return self.longestCommonSubsequence(text2, text1)

            dp = [[0 for _ in range(len(text2)+1)] for _ in range(2)]

            for i in range(1, len(text1)+1):
                for j in range(1, len(text2)+1):
                    dp[i%2][j] = dp[(i-1)%2][j-1]+1 if text1[i-1] == text2[j-1] \
                                                   else max(dp[(i-1)%2][j], dp[i%2][j-1])
            return dp[len(text1)%2][len(text2)]

        return len(s)-longestCommonSubsequence(s, s[::-1])

[5]:

sol = Solution1()

s = "zzazz"
assert sol.minInsertions(s) == 0

s = "mbadm"
assert sol.minInsertions(s) == 2

s = "leetcode"
assert sol.minInsertions(s) == 5

s = "g"
assert sol.minInsertions(s) == 0

s = "no"
assert sol.minInsertions(s) == 1